home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Exec 5 / CD_Magazyn_EXEC_nr_5.iso / eXec / Krotkie opisy / Programy / XADMaster / xad_bzip2.lha / bzip2.c < prev    next >
C/C++ Source or Header  |  2000-12-09  |  57KB  |  1,740 lines
  1. /* This XAD client is written by Kyzer/CSG <kyzer@4u.net>, the actual
  2.  * decompression code is written by bzip2's author, Julian Seward. bzip2
  3.  * is (C) 1996-2000 Julian R. Seward. Please see some of his files for more
  4.  * information.
  5.  *
  6.  * License:
  7.  * - The modified and unmodified code of libbzip2 is (C) Julian R. Seward
  8.  *   and retains its original license. However, you should not directly
  9.  *   use these modified versions, you should obtain the original bzip2
  10.  *   and libbzip2 from http://sourceware.cygnus.com/bzip2/
  11.  * - This contraction of the libbzip2 code and the XAD client section
  12.  *   is licensed under the GNU General public license, version 2.
  13.  */
  14.  
  15. /* bzip2, (C) 1996-2000 Julian R. Seward, is a "block-sorting file
  16.  * compressor". It uses the Burrows-Wheeler block-sorting text compression
  17.  * algorithm, with some Huffman coding on the output, and, run length encoding
  18.  * and randomisation thrown in to improve the speed efficiency of the
  19.  * compressor. The run-length encoding "is entirely irrelevant" and the
  20.  * randomisation "doesn't really need to be there". However, "compression is
  21.  * generally considerably better than that achieved by more conventional
  22.  * LZ77/LZ78-based compressors, and approaches the performance of the PPM
  23.  * family of statistical compressors."
  24.  *
  25.  * bzip2 is mainly used as a replacement for gzip in compressing UNIX tar
  26.  * archives, because it beats gzip (which uses the LZH-like deflate
  27.  * algorithim) in compression and is therefore useful for saving valuable
  28.  * bandwidth for Linux distributions and the like.
  29.  *
  30.  * The main 'problems' with bzip2 are:
  31.  * - it uses huge amounts of memory. The default compression mode is the
  32.  *   maximum block size, which means that decompression requires 2.1Mb of RAM
  33.  *   (preferably 3.5Mb), even for the tiniest files.
  34.  * - it can only compress and decompress single files - it doesn't store any
  35.  *   file metadata whatsoever, not even a single file's name or size.
  36.  * - it has no idea how large the output data is in advance, and it can't even
  37.  *   tell how big each block is in the file. It can only run through the data
  38.  *   and tell you once it's decompressed how big it was.
  39.  *
  40.  * Even with these problems, the advantage in compression over gzip is enough
  41.  * to make it popular with new archive sites.
  42.  *
  43.  * The original bzip2 and libbzip2 are available from
  44.  * http://sourceware.cygnus.com/bzip2/
  45.  */
  46.  
  47. /* bzip2 is actually just a file compressor, and doesn't even include any
  48.  * details about the file itself - perhaps this should be an XFD slave
  49.  * instead? A couple of reasons why not:
  50.  *
  51.  * 1. tar files are archives. gzip'ed tar files are archives too. 99% of
  52.  *    bzip2 compressed files are tar archives. therefore, if gzip is an xad
  53.  *    slave, bzip2 is an xad slave too.
  54.  *
  55.  * 2. bzip2 takes astonishing amounts of memory to unpack - it's far more a
  56.  *    UNIX archive compressor than it is a realtime depacker for demos and
  57.  *    games, which is the ethos of XFD compressors.
  58.  */
  59.  
  60. /* bzip2 file format:
  61.  * - first, the header: 'BZh1' to 'BZh9'
  62.  *   - the 1-9 in the header is the size of a block / 100000
  63.  *
  64.  * - next, 0 or more compressed data blocks
  65.  *   - the block starts with recogdata: $314159265359 (BCD pi :)
  66.  *   - then comes a 4 byte CRC-so-far
  67.  *   - then the various state tables
  68.  *   - then the sorted randomized huffed RLE data
  69.  *
  70.  * - a final block containing no data is always included
  71.  *   - it's recog is $177245385090, however after the first block
  72.  *     the data is 87.5% likely not to be byte aligned, so you probably
  73.  *     won't see it in a hex editor.
  74.  *   - there's a 4 byte final CRC, but for the reason mentioned above,
  75.  *     it's difficult to check.
  76.  *
  77.  * - minimum size of file is 14 bytes for a 0 byte input file (just a
  78.  *   header and the final block, no data blocks), or 37 bytes for a 1 byte
  79.  *   input file
  80.  *
  81.  * bzip2, by virtue of early recklessness and backwards compatibility on
  82.  * the part of the author, does not contain *any* information whatsoever
  83.  * about the data itself, it can't even know how long a block is without
  84.  * decompressing it. But hey! It beats gzip on compression, so that's got
  85.  * to be good, right?
  86.  */
  87.  
  88. /* CHANGES TO LIBBZIP2
  89.  *
  90.  * All files are collected into a single file.
  91.  * All superfluous header definitions are removed.
  92.  * All compression code and definitions are removed.
  93.  *
  94.  * The decompresser has been modified to try and enter 'small mode'
  95.  * automatically if it cannot allocate enough memory for 'fast mode'. The
  96.  * library normally expects you to say which mode you want and sticks rigidly
  97.  * to that.
  98.  *
  99.  * Assertion failures in decompression (that is, failures of the code that
  100.  * can't logically occur) are turned into returning error codes, as the XAD
  101.  * client can't support the immediate exit() that libbzip2 would like -
  102.  * instead we have to pop back to the original entry point and return, it's
  103.  * the only way.
  104.  *
  105.  * The random number table 'rNums' has been made into Int16 instead of Int32.
  106.  * This halves the size of the table (and saves exactly 1Kb), yet because all
  107.  * the numbers are small enough to fit into an Int16, it doesn't require
  108.  * changing code at all. All I've added is an explicit cast when a table entry
  109.  * is retrieved, to be on the safe side. This optimisation was suggested by
  110.  * Dirk Stöcker.
  111.  *
  112.  * The CRC table is now generated at runtime, saving another 1Kb. The code for
  113.  * this was written by Dirk Stöcker.
  114.  */
  115.  
  116. /* VERSION HISTORY
  117.  * 
  118.  * v1.0: original
  119.  * v1.1: uses XAD's new 'no size' flag and default name. Released with XAD 6.
  120.  * v1.2: now uses bzip2-1.0.0 sources.
  121.  * v1.3: uses XAD's new 'input archive filename'. Released with XAD 7.
  122.  * v1.4: generates CRC table at runtime, slightly better file extension code.
  123.  * v1.5: "trailing garbage after EOF ignored" non-error implemented. 68040
  124.  *       version and install script added.
  125.  *
  126.  * $VER: bzip2.c 1.5 (09.12.2000)
  127.  */
  128.  
  129. #include <libraries/xadmaster.h>
  130. #include <proto/xadmaster.h>
  131. #include <string.h>
  132. #include <stdlib.h>
  133.  
  134. #include "SDI_compiler.h"
  135.  
  136. #define XADBASE  REG(a6, struct xadMasterBase *xadMasterBase)
  137.  
  138. #ifndef XADMASTERFILE
  139. #define bzip2_Client        FirstClient
  140. #define NEXTCLIENT        0
  141. const UBYTE version[] = "$VER: bzip2 1.5 (09.12.2000)";
  142. #endif
  143. #define BZIP2_VERSION        1
  144. #define BZIP2_REVISION        5
  145.  
  146.  
  147. void BZ2_MakeCRC32R(ULONG *buf, ULONG ID) {
  148.   ULONG k;
  149.   int i, j;
  150.   for(i = 0; i < 256; i++) {
  151.     k = i << 24;
  152.     for(j=8; j--;) k = (k & 0x80000000) ? ((k << 1) ^ ID) : (k << 1);
  153.     buf[i] = k;
  154.   }
  155. }
  156.  
  157. /*--- bzip2 code ------------------------------------------------------------*/
  158.  
  159. /*--
  160.   This file is a part of bzip2 and/or libbzip2, a program and
  161.   library for lossless, block-sorting data compression.
  162.  
  163.   Copyright (C) 1996-2000 Julian R Seward.  All rights reserved.
  164.  
  165.   Redistribution and use in source and binary forms, with or without
  166.   modification, are permitted provided that the following conditions
  167.   are met:
  168.  
  169.   1. Redistributions of source code must retain the above copyright
  170.      notice, this list of conditions and the following disclaimer.
  171.  
  172.   2. The origin of this software must not be misrepresented; you must 
  173.      not claim that you wrote the original software.  If you use this 
  174.      software in a product, an acknowledgment in the product 
  175.      documentation would be appreciated but is not required.
  176.  
  177.   3. Altered source versions must be plainly marked as such, and must
  178.      not be misrepresented as being the original software.
  179.  
  180.   4. The name of the author may not be used to endorse or promote 
  181.      products derived from this software without specific prior written 
  182.      permission.
  183.  
  184.   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
  185.   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  186.   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  187.   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  188.   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  189.   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  190.   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  191.   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  192.   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  193.   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  194.   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  195.  
  196.   Julian Seward, Cambridge, UK.
  197.   jseward@acm.org
  198.   bzip2/libbzip2 version 1.0 of 21 March 2000
  199.  
  200.   This program is based on (at least) the work of:
  201.      Mike Burrows
  202.      David Wheeler
  203.      Peter Fenwick
  204.      Alistair Moffat
  205.      Radford Neal
  206.      Ian H. Witten
  207.      Robert Sedgewick
  208.      Jon L. Bentley
  209.  
  210.   For more information on these sources, see the manual.
  211. --*/
  212.  
  213. #define BZ_RUN               0
  214. #define BZ_FLUSH             1
  215. #define BZ_FINISH            2
  216.  
  217. #define BZ_OK                0
  218. #define BZ_RUN_OK            1
  219. #define BZ_FLUSH_OK          2
  220. #define BZ_FINISH_OK         3
  221. #define BZ_STREAM_END        4
  222. #define BZ_SEQUENCE_ERROR    (-1)
  223. #define BZ_PARAM_ERROR       (-2)
  224. #define BZ_MEM_ERROR         (-3)
  225. #define BZ_DATA_ERROR        (-4)
  226. #define BZ_DATA_ERROR_MAGIC  (-5)
  227. #define BZ_IO_ERROR          (-6)
  228. #define BZ_UNEXPECTED_EOF    (-7)
  229. #define BZ_OUTBUFF_FULL      (-8)
  230. #define BZ_CONFIG_ERROR      (-9)
  231.  
  232. typedef 
  233.    struct {
  234.       char *next_in;
  235.       unsigned int avail_in;
  236.       unsigned int total_in_lo32;
  237.       unsigned int total_in_hi32;
  238.  
  239.       char *next_out;
  240.       unsigned int avail_out;
  241.       unsigned int total_out_lo32;
  242.       unsigned int total_out_hi32;
  243.  
  244.       void *state;
  245.  
  246.       void *(*bzalloc)(void *,int,int);
  247.       void (*bzfree)(void *,void *);
  248.       void *opaque;
  249.    } 
  250.    bz_stream;
  251.  
  252. /*-- General stuff. --*/
  253.  
  254. #define BZ_VERSION  "1.0.0, 16-May-2000"
  255.  
  256. #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
  257. #define BZFREE(ppp)  (strm->bzfree)(strm->opaque,(ppp))
  258.  
  259.  
  260. /*-- Constants for the back end. --*/
  261.  
  262. #define BZ_MAX_ALPHA_SIZE 258
  263. #define BZ_MAX_CODE_LEN    23
  264.  
  265. #define BZ_RUNA 0
  266. #define BZ_RUNB 1
  267.  
  268. #define BZ_N_GROUPS 6
  269. #define BZ_G_SIZE   50
  270. #define BZ_N_ITERS  4
  271.  
  272. #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
  273.  
  274. /*-- Stuff for randomising repetitive blocks. --*/
  275.  
  276. #define BZ_RAND_DECLS                          \
  277.    LONG rNToGo;                               \
  278.    LONG rTPos                                 \
  279.  
  280. #define BZ_RAND_INIT_MASK                      \
  281.    s->rNToGo = 0;                              \
  282.    s->rTPos  = 0                               \
  283.  
  284. #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
  285.  
  286. #define BZ_RAND_UPD_MASK                       \
  287.    if (s->rNToGo == 0) {                       \
  288.       s->rNToGo = (LONG) BZ2_rNums[s->rTPos]; \
  289.       s->rTPos++;                              \
  290.       if (s->rTPos == 512) s->rTPos = 0;       \
  291.    }                                           \
  292.    s->rNToGo--;
  293.  
  294.  
  295.  
  296. /*-- Stuff for doing CRCs. --*/
  297.  
  298. #define BZ_INITIALISE_CRC(crcVar)              \
  299. {                                              \
  300.    crcVar = 0xffffffffL;                       \
  301. }
  302.  
  303. #define BZ_FINALISE_CRC(crcVar)                \
  304. {                                              \
  305.    crcVar = ~(crcVar);                         \
  306. }
  307.  
  308. #define BZ_UPDATE_CRC(crcVar,cha)              \
  309. {                                              \
  310.    crcVar = (crcVar << 8) ^                    \
  311.             BZ2_crc32Table[(crcVar >> 24) ^    \
  312.                            ((UBYTE)cha)];      \
  313. }
  314.  
  315. /*-- states for decompression. --*/
  316.  
  317. #define BZ_X_IDLE        1
  318. #define BZ_X_OUTPUT      2
  319.  
  320. #define BZ_X_MAGIC_1     10
  321. #define BZ_X_MAGIC_2     11
  322. #define BZ_X_MAGIC_3     12
  323. #define BZ_X_MAGIC_4     13
  324. #define BZ_X_BLKHDR_1    14
  325. #define BZ_X_BLKHDR_2    15
  326. #define BZ_X_BLKHDR_3    16
  327. #define BZ_X_BLKHDR_4    17
  328. #define BZ_X_BLKHDR_5    18
  329. #define BZ_X_BLKHDR_6    19
  330. #define BZ_X_BCRC_1      20
  331. #define BZ_X_BCRC_2      21
  332. #define BZ_X_BCRC_3      22
  333. #define BZ_X_BCRC_4      23
  334. #define BZ_X_RANDBIT     24
  335. #define BZ_X_ORIGPTR_1   25
  336. #define BZ_X_ORIGPTR_2   26
  337. #define BZ_X_ORIGPTR_3   27
  338. #define BZ_X_MAPPING_1   28
  339. #define BZ_X_MAPPING_2   29
  340. #define BZ_X_SELECTOR_1  30
  341. #define BZ_X_SELECTOR_2  31
  342. #define BZ_X_SELECTOR_3  32
  343. #define BZ_X_CODING_1    33
  344. #define BZ_X_CODING_2    34
  345. #define BZ_X_CODING_3    35
  346. #define BZ_X_MTF_1       36
  347. #define BZ_X_MTF_2       37
  348. #define BZ_X_MTF_3       38
  349. #define BZ_X_MTF_4       39
  350. #define BZ_X_MTF_5       40
  351. #define BZ_X_MTF_6       41
  352. #define BZ_X_ENDHDR_2    42
  353. #define BZ_X_ENDHDR_3    43
  354. #define BZ_X_ENDHDR_4    44
  355. #define BZ_X_ENDHDR_5    45
  356. #define BZ_X_ENDHDR_6    46
  357. #define BZ_X_CCRC_1      47
  358. #define BZ_X_CCRC_2      48
  359. #define BZ_X_CCRC_3      49
  360. #define BZ_X_CCRC_4      50
  361.  
  362. /*-- Constants for the fast MTF decoder. --*/
  363.  
  364. #define MTFA_SIZE 4096
  365. #define MTFL_SIZE 16
  366.  
  367. /*-- Structure holding all the decompression-side stuff. --*/
  368.  
  369. typedef
  370.    struct {
  371.       /* pointer back to the struct bz_stream */
  372.       bz_stream* strm;
  373.  
  374.       /* state indicator for this stream */
  375.       LONG    state;
  376.  
  377.       /* for doing the final run-length decoding */
  378.       UBYTE    state_out_ch;
  379.       LONG    state_out_len;
  380.       BOOL     blockRandomised;
  381.       BZ_RAND_DECLS;
  382.  
  383.       /* the buffer for bit stream reading */
  384.       ULONG   bsBuff;
  385.       LONG    bsLive;
  386.  
  387.       /* misc administratium */
  388.       LONG    blockSize100k;
  389.       BOOL     smallDecompress;
  390.       LONG    currBlockNo;
  391.       LONG    verbosity;
  392.  
  393.       /* for undoing the Burrows-Wheeler transform */
  394.       LONG    origPtr;
  395.       ULONG   tPos;
  396.       LONG    k0;
  397.       LONG    unzftab[256];
  398.       LONG    nblock_used;
  399.       LONG    cftab[257];
  400.       LONG    cftabCopy[257];
  401.  
  402.       /* for undoing the Burrows-Wheeler transform (FAST) */
  403.       ULONG   *tt;
  404.  
  405.       /* for undoing the Burrows-Wheeler transform (SMALL) */
  406.       UWORD   *ll16;
  407.       UBYTE    *ll4;
  408.  
  409.       /* stored and calculated CRCs */
  410.       ULONG   storedBlockCRC;
  411.       ULONG   storedCombinedCRC;
  412.       ULONG   calculatedBlockCRC;
  413.       ULONG   calculatedCombinedCRC;
  414.  
  415.       /* map of bytes used in block */
  416.       LONG    nInUse;
  417.       BOOL     inUse[256];
  418.       BOOL     inUse16[16];
  419.       UBYTE    seqToUnseq[256];
  420.  
  421.       /* for decoding the MTF values */
  422.       UBYTE    mtfa   [MTFA_SIZE];
  423.       LONG    mtfbase[256 / MTFL_SIZE];
  424.       UBYTE    selector   [BZ_MAX_SELECTORS];
  425.       UBYTE    selectorMtf[BZ_MAX_SELECTORS];
  426.       UBYTE    len  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
  427.  
  428.       LONG    limit  [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
  429.       LONG    base   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
  430.       LONG    perm   [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
  431.       LONG    minLens[BZ_N_GROUPS];
  432.  
  433.       /* save area for scalars in the main decompress code */
  434.       LONG    save_i;
  435.       LONG    save_j;
  436.       LONG    save_t;
  437.       LONG    save_alphaSize;
  438.       LONG    save_nGroups;
  439.       LONG    save_nSelectors;
  440.       LONG    save_EOB;
  441.       LONG    save_groupNo;
  442.       LONG    save_groupPos;
  443.       LONG    save_nextSym;
  444.       LONG    save_nblockMAX;
  445.       LONG    save_nblock;
  446.       LONG    save_es;
  447.       LONG    save_N;
  448.       LONG    save_curr;
  449.       LONG    save_zt;
  450.       LONG    save_zn; 
  451.       LONG    save_zvec;
  452.       LONG    save_zj;
  453.       LONG    save_gSel;
  454.       LONG    save_gMinlen;
  455.       LONG*   save_gLimit;
  456.       LONG*   save_gBase;
  457.       LONG*   save_gPerm;
  458.  
  459.    }
  460.    DState;
  461.  
  462.  
  463.  
  464. /*-- Macros for decompression. --*/
  465.  
  466. #define BZ_GET_FAST(cccc)                     \
  467.     s->tPos = s->tt[s->tPos];                 \
  468.     cccc = (UBYTE)(s->tPos & 0xff);           \
  469.     s->tPos >>= 8;
  470.  
  471. #define BZ_GET_FAST_C(cccc)                   \
  472.     c_tPos = c_tt[c_tPos];                    \
  473.     cccc = (UBYTE)(c_tPos & 0xff);            \
  474.     c_tPos >>= 8;
  475.  
  476. #define SET_LL4(i,n)                                          \
  477.    { if (((i) & 0x1) == 0)                                    \
  478.         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else    \
  479.         s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
  480.    }
  481.  
  482. #define GET_LL4(i)                             \
  483.    ((((ULONG)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
  484.  
  485. #define SET_LL(i,n)                          \
  486.    { s->ll16[i] = (UWORD)(n & 0x0000ffff);  \
  487.      SET_LL4(i, n >> 16);                    \
  488.    }
  489.  
  490. #define GET_LL(i) \
  491.    (((ULONG)s->ll16[i]) | (GET_LL4(i) << 16))
  492.  
  493. #define BZ_GET_SMALL(cccc)                            \
  494.       cccc = BZ2_indexIntoF ( s->tPos, s->cftab );    \
  495.       s->tPos = GET_LL(s->tPos);
  496.  
  497. ULONG BZ2_crc32Table[256];
  498.  
  499. static WORD BZ2_rNums[512] = { 
  500.   619, 720, 127, 481, 931, 816, 813, 233, 566, 247, 985, 724, 205, 454, 863,
  501.   491, 741, 242, 949, 214, 733, 859, 335, 708, 621, 574,  73, 654, 730, 472,
  502.   419, 436, 278, 496, 867, 210, 399, 680, 480,  51, 878, 465, 811, 169, 869,
  503.   675, 611, 697, 867, 561, 862, 687, 507, 283, 482, 129, 807, 591, 733, 623,
  504.   150, 238,  59, 379, 684, 877, 625, 169, 643, 105, 170, 607, 520, 932, 727,
  505.   476, 693, 425, 174, 647,  73, 122, 335, 530, 442, 853, 695, 249, 445, 515,
  506.   909, 545, 703, 919, 874, 474, 882, 500, 594, 612, 641, 801, 220, 162, 819,
  507.   984, 589, 513, 495, 799, 161, 604, 958, 533, 221, 400, 386, 867, 600, 782,
  508.   382, 596, 414, 171, 516, 375, 682, 485, 911, 276,  98, 553, 163, 354, 666,
  509.   933, 424, 341, 533, 870, 227, 730, 475, 186, 263, 647, 537, 686, 600, 224,
  510.   469,  68, 770, 919, 190, 373, 294, 822, 808, 206, 184, 943, 795, 384, 383,
  511.   461, 404, 758, 839, 887, 715,  67, 618, 276, 204, 918, 873, 777, 604, 560,
  512.   951, 160, 578, 722,  79, 804,  96, 409, 713, 940, 652, 934, 970, 447, 318,
  513.   353, 859, 672, 112, 785, 645, 863, 803, 350, 139,  93, 354,  99, 820, 908,
  514.   609, 772, 154, 274, 580, 184,  79, 626, 630, 742, 653, 282, 762, 623, 680,
  515.    81, 927, 626, 789, 125, 411, 521, 938, 300, 821,  78, 343, 175, 128, 250,
  516.   170, 774, 972, 275, 999, 639, 495,  78, 352, 126, 857, 956, 358, 619, 580,
  517.   124, 737, 594, 701, 612, 669, 112, 134, 694, 363, 992, 809, 743, 168, 974,
  518.   944, 375, 748,  52, 600, 747, 642, 182, 862,  81, 344, 805, 988, 739, 511,
  519.   655, 814, 334, 249, 515, 897, 955, 664, 981, 649, 113, 974, 459, 893, 228,
  520.   433, 837, 553, 268, 926, 240, 102, 654, 459,  51, 686, 754, 806, 760, 493,
  521.   403, 415, 394, 687, 700, 946, 670, 656, 610, 738, 392, 760, 799, 887, 653,
  522.   978, 321, 576, 617, 626, 502, 894, 679, 243, 440, 680, 879, 194, 572, 640,
  523.   724, 926,  56, 204, 700, 707, 151, 457, 449, 797, 195, 791, 558, 945, 679,
  524.   297,  59,  87, 824, 713, 663, 412, 693, 342, 606, 134, 108, 571, 364, 631,
  525.   212, 174, 643, 304, 329, 343,  97, 430, 751, 497, 314, 983, 374, 822, 928,
  526.   140, 206,  73, 263, 980, 736, 876, 478, 430, 305, 170, 514, 364, 692, 829,
  527.    82, 855, 953, 676, 246, 369, 970, 294, 750, 807, 827, 150, 790, 288, 923,
  528.   804, 378, 215, 828, 592, 281, 565, 555, 710,  82, 896, 831, 547, 261, 524,
  529.   462, 293, 465, 502,  56, 661, 821, 976, 991, 658, 869, 905, 758, 745, 193,
  530.   768, 550, 608, 933, 378, 286, 215, 979, 792, 961,  61, 688, 793, 644, 986,
  531.   403, 106, 366, 905, 644, 372, 567, 466, 434, 645, 210, 389, 550, 919, 135,
  532.   780, 773, 635, 389, 707, 100, 626, 958, 165, 504, 920, 176, 193, 713, 857,
  533.   265, 203,  50, 668, 108, 645, 990, 626, 197, 510, 357, 358, 850, 858, 364,
  534.   936, 638
  535. };
  536.  
  537. void BZ2_hbCreateDecodeTables ( LONG *limit, LONG *base, LONG *perm,
  538. UBYTE *length, LONG minLen, LONG maxLen, LONG alphaSize ) {
  539.    LONG pp, i, j, vec;
  540.  
  541.    pp = 0;
  542.    for (i = minLen; i <= maxLen; i++)
  543.       for (j = 0; j < alphaSize; j++)
  544.          if (length[j] == i) { perm[pp] = j; pp++; };
  545.  
  546.    for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
  547.    for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
  548.    for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
  549.    for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
  550.    vec = 0;
  551.  
  552.    for (i = minLen; i <= maxLen; i++) {
  553.       vec += (base[i+1] - base[i]);
  554.       limit[i] = vec-1;
  555.       vec <<= 1;
  556.    }
  557.    for (i = minLen + 1; i <= maxLen; i++)
  558.       base[i] = ((limit[i-1] + 1) << 1) - base[i];
  559. }
  560.  
  561. /*---------------------------------------------------*/
  562. static
  563. void makeMaps_d ( DState* s )
  564. {
  565.    LONG i;
  566.    s->nInUse = 0;
  567.    for (i = 0; i < 256; i++)
  568.       if (s->inUse[i]) {
  569.          s->seqToUnseq[s->nInUse] = i;
  570.          s->nInUse++;
  571.       }
  572. }
  573.  
  574.  
  575. /*---------------------------------------------------*/
  576. #define RETURN(rrr)                               \
  577.    { retVal = rrr; goto save_state_and_return; };
  578.  
  579. #define GET_BITS(lll,vvv,nnn)                     \
  580.    case lll: s->state = lll;                      \
  581.    while (TRUE) {                                 \
  582.       if (s->bsLive >= nnn) {                     \
  583.          ULONG v;                                \
  584.          v = (s->bsBuff >>                        \
  585.              (s->bsLive-nnn)) & ((1 << nnn)-1);   \
  586.          s->bsLive -= nnn;                        \
  587.          vvv = v;                                 \
  588.          break;                                   \
  589.       }                                           \
  590.       if (s->strm->avail_in == 0) RETURN(BZ_OK);  \
  591.       s->bsBuff                                   \
  592.          = (s->bsBuff << 8) |                     \
  593.            ((ULONG)                              \
  594.               (*((UBYTE*)(s->strm->next_in))));   \
  595.       s->bsLive += 8;                             \
  596.       s->strm->next_in++;                         \
  597.       s->strm->avail_in--;                        \
  598.       s->strm->total_in_lo32++;                   \
  599.       if (s->strm->total_in_lo32 == 0)            \
  600.          s->strm->total_in_hi32++;                \
  601.    }
  602.  
  603. #define GET_UCHAR(lll,uuu)                        \
  604.    GET_BITS(lll,uuu,8)
  605.  
  606. #define GET_BIT(lll,uuu)                          \
  607.    GET_BITS(lll,uuu,1)
  608.  
  609. /*---------------------------------------------------*/
  610. #define GET_MTF_VAL(label1,label2,lval)           \
  611. {                                                 \
  612.    if (groupPos == 0) {                           \
  613.       groupNo++;                                  \
  614.       if (groupNo >= nSelectors)                  \
  615.          RETURN(BZ_DATA_ERROR);                   \
  616.       groupPos = BZ_G_SIZE;                       \
  617.       gSel = s->selector[groupNo];                \
  618.       gMinlen = s->minLens[gSel];                 \
  619.       gLimit = &(s->limit[gSel][0]);              \
  620.       gPerm = &(s->perm[gSel][0]);                \
  621.       gBase = &(s->base[gSel][0]);                \
  622.    }                                              \
  623.    groupPos--;                                    \
  624.    zn = gMinlen;                                  \
  625.    GET_BITS(label1, zvec, zn);                    \
  626.    while (1) {                                    \
  627.       if (zn > 20 /* the longest code */)         \
  628.          RETURN(BZ_DATA_ERROR);                   \
  629.       if (zvec <= gLimit[zn]) break;              \
  630.       zn++;                                       \
  631.       GET_BIT(label2, zj);                        \
  632.       zvec = (zvec << 1) | zj;                    \
  633.    };                                             \
  634.    if (zvec - gBase[zn] < 0                       \
  635.        || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE)  \
  636.       RETURN(BZ_DATA_ERROR);                      \
  637.    lval = gPerm[zvec - gBase[zn]];                \
  638. }
  639.  
  640.  
  641. /*---------------------------------------------------*/
  642. INLINE LONG BZ2_indexIntoF ( LONG indx, LONG *cftab )
  643. {
  644.    LONG nb, na, mid;
  645.    nb = 0;
  646.    na = 256;
  647.    do {
  648.       mid = (nb + na) >> 1;
  649.       if (indx >= cftab[mid]) nb = mid; else na = mid;
  650.    }
  651.    while (na - nb != 1);
  652.    return nb;
  653. }
  654.  
  655.  
  656. /*---------------------------------------------------*/
  657. LONG BZ2_decompress ( DState* s )
  658. {
  659.    UBYTE      uc;
  660.    LONG      retVal;
  661.    LONG      minLen, maxLen;
  662.    bz_stream* strm = s->strm;
  663.  
  664.    /* stuff that needs to be saved/restored */
  665.    LONG  i;
  666.    LONG  j;
  667.    LONG  t;
  668.    LONG  alphaSize;
  669.    LONG  nGroups;
  670.    LONG  nSelectors;
  671.    LONG  EOB;
  672.    LONG  groupNo;
  673.    LONG  groupPos;
  674.    LONG  nextSym;
  675.    LONG  nblockMAX;
  676.    LONG  nblock;
  677.    LONG  es;
  678.    LONG  N;
  679.    LONG  curr;
  680.    LONG  zt;
  681.    LONG  zn; 
  682.    LONG  zvec;
  683.    LONG  zj;
  684.    LONG  gSel;
  685.    LONG  gMinlen;
  686.    LONG* gLimit;
  687.    LONG* gBase;
  688.    LONG* gPerm;
  689.  
  690.    if (s->state == BZ_X_MAGIC_1) {
  691.       /*initialise the save area*/
  692.       s->save_i           = 0;
  693.       s->save_j           = 0;
  694.       s->save_t           = 0;
  695.       s->save_alphaSize   = 0;
  696.       s->save_nGroups     = 0;
  697.       s->save_nSelectors  = 0;
  698.       s->save_EOB         = 0;
  699.       s->save_groupNo     = 0;
  700.       s->save_groupPos    = 0;
  701.       s->save_nextSym     = 0;
  702.       s->save_nblockMAX   = 0;
  703.       s->save_nblock      = 0;
  704.       s->save_es          = 0;
  705.       s->save_N           = 0;
  706.       s->save_curr        = 0;
  707.       s->save_zt          = 0;
  708.       s->save_zn          = 0;
  709.       s->save_zvec        = 0;
  710.       s->save_zj          = 0;
  711.       s->save_gSel        = 0;
  712.       s->save_gMinlen     = 0;
  713.       s->save_gLimit      = NULL;
  714.       s->save_gBase       = NULL;
  715.       s->save_gPerm       = NULL;
  716.    }
  717.  
  718.    /*restore from the save area*/
  719.    i           = s->save_i;
  720.    j           = s->save_j;
  721.    t           = s->save_t;
  722.    alphaSize   = s->save_alphaSize;
  723.    nGroups     = s->save_nGroups;
  724.    nSelectors  = s->save_nSelectors;
  725.    EOB         = s->save_EOB;
  726.    groupNo     = s->save_groupNo;
  727.    groupPos    = s->save_groupPos;
  728.    nextSym     = s->save_nextSym;
  729.    nblockMAX   = s->save_nblockMAX;
  730.    nblock      = s->save_nblock;
  731.    es          = s->save_es;
  732.    N           = s->save_N;
  733.    curr        = s->save_curr;
  734.    zt          = s->save_zt;
  735.    zn          = s->save_zn; 
  736.    zvec        = s->save_zvec;
  737.    zj          = s->save_zj;
  738.    gSel        = s->save_gSel;
  739.    gMinlen     = s->save_gMinlen;
  740.    gLimit      = s->save_gLimit;
  741.    gBase       = s->save_gBase;
  742.    gPerm       = s->save_gPerm;
  743.  
  744.    retVal = BZ_OK;
  745.  
  746.    switch (s->state) {
  747.  
  748.       GET_UCHAR(BZ_X_MAGIC_1, uc);
  749.       if (uc != 'B') RETURN(BZ_DATA_ERROR_MAGIC);
  750.  
  751.       GET_UCHAR(BZ_X_MAGIC_2, uc);
  752.       if (uc != 'Z') RETURN(BZ_DATA_ERROR_MAGIC);
  753.  
  754.       GET_UCHAR(BZ_X_MAGIC_3, uc)
  755.       if (uc != 'h') RETURN(BZ_DATA_ERROR_MAGIC);
  756.  
  757.       GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
  758.       if (s->blockSize100k < '1' || 
  759.           s->blockSize100k > '9') RETURN(BZ_DATA_ERROR_MAGIC);
  760.       s->blockSize100k -= '0';
  761.  
  762.       /* drops down to small mode if need be */
  763.       if (!s->smallDecompress) {
  764.          s->tt  = BZALLOC( s->blockSize100k * 100000 * sizeof(LONG) );
  765.          if (s->tt == NULL) s->smallDecompress = TRUE;
  766.       }
  767.       if (s->smallDecompress) {
  768.  
  769.          s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UWORD) );
  770.          s->ll4  = BZALLOC( 
  771.                       ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UBYTE) 
  772.                    );
  773.          if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
  774.       }
  775.  
  776.       GET_UCHAR(BZ_X_BLKHDR_1, uc);
  777.  
  778.       if (uc == 0x17) goto endhdr_2;
  779.       if (uc != 0x31) RETURN(BZ_DATA_ERROR);
  780.       GET_UCHAR(BZ_X_BLKHDR_2, uc);
  781.       if (uc != 0x41) RETURN(BZ_DATA_ERROR);
  782.       GET_UCHAR(BZ_X_BLKHDR_3, uc);
  783.       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
  784.       GET_UCHAR(BZ_X_BLKHDR_4, uc);
  785.       if (uc != 0x26) RETURN(BZ_DATA_ERROR);
  786.       GET_UCHAR(BZ_X_BLKHDR_5, uc);
  787.       if (uc != 0x53) RETURN(BZ_DATA_ERROR);
  788.       GET_UCHAR(BZ_X_BLKHDR_6, uc);
  789.       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
  790.  
  791.       s->currBlockNo++;
  792.  
  793.       s->storedBlockCRC = 0;
  794.       GET_UCHAR(BZ_X_BCRC_1, uc);
  795.       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((ULONG)uc);
  796.       GET_UCHAR(BZ_X_BCRC_2, uc);
  797.       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((ULONG)uc);
  798.       GET_UCHAR(BZ_X_BCRC_3, uc);
  799.       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((ULONG)uc);
  800.       GET_UCHAR(BZ_X_BCRC_4, uc);
  801.       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((ULONG)uc);
  802.  
  803.       GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
  804.  
  805.       s->origPtr = 0;
  806.       GET_UCHAR(BZ_X_ORIGPTR_1, uc);
  807.       s->origPtr = (s->origPtr << 8) | ((LONG)uc);
  808.       GET_UCHAR(BZ_X_ORIGPTR_2, uc);
  809.       s->origPtr = (s->origPtr << 8) | ((LONG)uc);
  810.       GET_UCHAR(BZ_X_ORIGPTR_3, uc);
  811.       s->origPtr = (s->origPtr << 8) | ((LONG)uc);
  812.  
  813.       if (s->origPtr < 0)
  814.          RETURN(BZ_DATA_ERROR);
  815.       if (s->origPtr > 10 + 100000*s->blockSize100k) 
  816.          RETURN(BZ_DATA_ERROR);
  817.  
  818.       /*--- Receive the mapping table ---*/
  819.       for (i = 0; i < 16; i++) {
  820.          GET_BIT(BZ_X_MAPPING_1, uc);
  821.          if (uc == 1) 
  822.             s->inUse16[i] = TRUE; else 
  823.             s->inUse16[i] = FALSE;
  824.       }
  825.  
  826.       for (i = 0; i < 256; i++) s->inUse[i] = FALSE;
  827.  
  828.       for (i = 0; i < 16; i++)
  829.          if (s->inUse16[i])
  830.             for (j = 0; j < 16; j++) {
  831.                GET_BIT(BZ_X_MAPPING_2, uc);
  832.                if (uc == 1) s->inUse[i * 16 + j] = TRUE;
  833.             }
  834.       makeMaps_d ( s );
  835.       if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
  836.       alphaSize = s->nInUse+2;
  837.  
  838.       /*--- Now the selectors ---*/
  839.       GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
  840.       if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
  841.       GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
  842.       if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
  843.       for (i = 0; i < nSelectors; i++) {
  844.          j = 0;
  845.          while (TRUE) {
  846.             GET_BIT(BZ_X_SELECTOR_3, uc);
  847.             if (uc == 0) break;
  848.             j++;
  849.             if (j >= nGroups) RETURN(BZ_DATA_ERROR);
  850.          }
  851.          s->selectorMtf[i] = j;
  852.       }
  853.  
  854.       /*--- Undo the MTF values for the selectors. ---*/
  855.       {
  856.          UBYTE pos[BZ_N_GROUPS], tmp, v;
  857.          for (v = 0; v < nGroups; v++) pos[v] = v;
  858.    
  859.          for (i = 0; i < nSelectors; i++) {
  860.             v = s->selectorMtf[i];
  861.             tmp = pos[v];
  862.             while (v > 0) { pos[v] = pos[v-1]; v--; }
  863.             pos[0] = tmp;
  864.             s->selector[i] = tmp;
  865.          }
  866.       }
  867.  
  868.       /*--- Now the coding tables ---*/
  869.       for (t = 0; t < nGroups; t++) {
  870.          GET_BITS(BZ_X_CODING_1, curr, 5);
  871.          for (i = 0; i < alphaSize; i++) {
  872.             while (TRUE) {
  873.                if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
  874.                GET_BIT(BZ_X_CODING_2, uc);
  875.                if (uc == 0) break;
  876.                GET_BIT(BZ_X_CODING_3, uc);
  877.                if (uc == 0) curr++; else curr--;
  878.             }
  879.             s->len[t][i] = curr;
  880.          }
  881.       }
  882.  
  883.       /*--- Create the Huffman decoding tables ---*/
  884.       for (t = 0; t < nGroups; t++) {
  885.          minLen = 32;
  886.          maxLen = 0;
  887.          for (i = 0; i < alphaSize; i++) {
  888.             if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
  889.             if (s->len[t][i] < minLen) minLen = s->len[t][i];
  890.          }
  891.          BZ2_hbCreateDecodeTables ( 
  892.             &(s->limit[t][0]), 
  893.             &(s->base[t][0]), 
  894.             &(s->perm[t][0]), 
  895.             &(s->len[t][0]),
  896.             minLen, maxLen, alphaSize
  897.          );
  898.          s->minLens[t] = minLen;
  899.       }
  900.  
  901.       /*--- Now the MTF values ---*/
  902.  
  903.       EOB      = s->nInUse+1;
  904.       nblockMAX = 100000 * s->blockSize100k;
  905.       groupNo  = -1;
  906.       groupPos = 0;
  907.  
  908.       for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
  909.  
  910.       /*-- MTF init --*/
  911.       {
  912.          LONG ii, jj, kk;
  913.          kk = MTFA_SIZE-1;
  914.          for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
  915.             for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
  916.                s->mtfa[kk] = (UBYTE)(ii * MTFL_SIZE + jj);
  917.                kk--;
  918.             }
  919.             s->mtfbase[ii] = kk + 1;
  920.          }
  921.       }
  922.       /*-- end MTF init --*/
  923.  
  924.       nblock = 0;
  925.       GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
  926.  
  927.       while (TRUE) {
  928.  
  929.          if (nextSym == EOB) break;
  930.  
  931.          if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
  932.  
  933.             es = -1;
  934.             N = 1;
  935.             do {
  936.                if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
  937.                if (nextSym == BZ_RUNB) es = es + (1+1) * N;
  938.                N = N * 2;
  939.                GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
  940.             }
  941.                while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
  942.  
  943.             es++;
  944.             uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
  945.             s->unzftab[uc] += es;
  946.  
  947.             if (s->smallDecompress)
  948.                while (es > 0) {
  949.                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
  950.                   s->ll16[nblock] = (UWORD)uc;
  951.                   nblock++;
  952.                   es--;
  953.                }
  954.             else
  955.                while (es > 0) {
  956.                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
  957.                   s->tt[nblock] = (ULONG)uc;
  958.                   nblock++;
  959.                   es--;
  960.                };
  961.  
  962.             continue;
  963.  
  964.          } else {
  965.  
  966.             if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
  967.  
  968.             /*-- uc = MTF ( nextSym-1 ) --*/
  969.             {
  970.                LONG ii, jj, kk, pp, lno, off;
  971.                ULONG nn;
  972.                nn = (ULONG)(nextSym - 1);
  973.  
  974.                if (nn < MTFL_SIZE) {
  975.                   /* avoid general-case expense */
  976.                   pp = s->mtfbase[0];
  977.                   uc = s->mtfa[pp+nn];
  978.                   while (nn > 3) {
  979.                      LONG z = pp+nn;
  980.                      s->mtfa[(z)  ] = s->mtfa[(z)-1];
  981.                      s->mtfa[(z)-1] = s->mtfa[(z)-2];
  982.                      s->mtfa[(z)-2] = s->mtfa[(z)-3];
  983.                      s->mtfa[(z)-3] = s->mtfa[(z)-4];
  984.                      nn -= 4;
  985.                   }
  986.                   while (nn > 0) { 
  987.                      s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 
  988.                   };
  989.                   s->mtfa[pp] = uc;
  990.                } else { 
  991.                   /* general case */
  992.                   lno = nn / MTFL_SIZE;
  993.                   off = nn % MTFL_SIZE;
  994.                   pp = s->mtfbase[lno] + off;
  995.                   uc = s->mtfa[pp];
  996.                   while (pp > s->mtfbase[lno]) { 
  997.                      s->mtfa[pp] = s->mtfa[pp-1]; pp--; 
  998.                   };
  999.                   s->mtfbase[lno]++;
  1000.                   while (lno > 0) {
  1001.                      s->mtfbase[lno]--;
  1002.                      s->mtfa[s->mtfbase[lno]] 
  1003.                         = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
  1004.                      lno--;
  1005.                   }
  1006.                   s->mtfbase[0]--;
  1007.                   s->mtfa[s->mtfbase[0]] = uc;
  1008.                   if (s->mtfbase[0] == 0) {
  1009.                      kk = MTFA_SIZE-1;
  1010.                      for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
  1011.                         for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
  1012.                            s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
  1013.                            kk--;
  1014.                         }
  1015.                         s->mtfbase[ii] = kk + 1;
  1016.                      }
  1017.                   }
  1018.                }
  1019.             }
  1020.             /*-- end uc = MTF ( nextSym-1 ) --*/
  1021.  
  1022.             s->unzftab[s->seqToUnseq[uc]]++;
  1023.             if (s->smallDecompress)
  1024.                s->ll16[nblock] = (UWORD)(s->seqToUnseq[uc]); else
  1025.                s->tt[nblock]   = (ULONG)(s->seqToUnseq[uc]);
  1026.             nblock++;
  1027.  
  1028.             GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
  1029.             continue;
  1030.          }
  1031.       }
  1032.  
  1033.       /* Now we know what nblock is, we can do a better sanity
  1034.          check on s->origPtr.
  1035.       */
  1036.       if (s->origPtr < 0 || s->origPtr >= nblock)
  1037.          RETURN(BZ_DATA_ERROR);
  1038.  
  1039.       s->state_out_len = 0;
  1040.       s->state_out_ch  = 0;
  1041.       BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
  1042.       s->state = BZ_X_OUTPUT;
  1043.  
  1044.       /*-- Set up cftab to facilitate generation of T^(-1) --*/
  1045.       s->cftab[0] = 0;
  1046.       for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
  1047.       for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
  1048.  
  1049.       if (s->smallDecompress) {
  1050.  
  1051.          /*-- Make a copy of cftab, used in generation of T --*/
  1052.          for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
  1053.  
  1054.          /*-- compute the T vector --*/
  1055.          for (i = 0; i < nblock; i++) {
  1056.             uc = (UBYTE)(s->ll16[i]);
  1057.             SET_LL(i, s->cftabCopy[uc]);
  1058.             s->cftabCopy[uc]++;
  1059.          }
  1060.  
  1061.          /*-- Compute T^(-1) by pointer reversal on T --*/
  1062.          i = s->origPtr;
  1063.          j = GET_LL(i);
  1064.          do {
  1065.             LONG tmp = GET_LL(j);
  1066.             SET_LL(j, i);
  1067.             i = j;
  1068.             j = tmp;
  1069.          }
  1070.             while (i != s->origPtr);
  1071.  
  1072.          s->tPos = s->origPtr;
  1073.          s->nblock_used = 0;
  1074.          if (s->blockRandomised) {
  1075.             BZ_RAND_INIT_MASK;
  1076.             BZ_GET_SMALL(s->k0); s->nblock_used++;
  1077.             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 
  1078.          } else {
  1079.             BZ_GET_SMALL(s->k0); s->nblock_used++;
  1080.          }
  1081.  
  1082.       } else {
  1083.  
  1084.          /*-- compute the T^(-1) vector --*/
  1085.          for (i = 0; i < nblock; i++) {
  1086.             uc = (UBYTE)(s->tt[i] & 0xff);
  1087.             s->tt[s->cftab[uc]] |= (i << 8);
  1088.             s->cftab[uc]++;
  1089.          }
  1090.  
  1091.          s->tPos = s->tt[s->origPtr] >> 8;
  1092.          s->nblock_used = 0;
  1093.          if (s->blockRandomised) {
  1094.             BZ_RAND_INIT_MASK;
  1095.             BZ_GET_FAST(s->k0); s->nblock_used++;
  1096.             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 
  1097.          } else {
  1098.             BZ_GET_FAST(s->k0); s->nblock_used++;
  1099.          }
  1100.  
  1101.       }
  1102.  
  1103.       RETURN(BZ_OK);
  1104.  
  1105.  
  1106.  
  1107.     endhdr_2:
  1108.  
  1109.       GET_UCHAR(BZ_X_ENDHDR_2, uc);
  1110.       if (uc != 0x72) RETURN(BZ_DATA_ERROR);
  1111.       GET_UCHAR(BZ_X_ENDHDR_3, uc);
  1112.       if (uc != 0x45) RETURN(BZ_DATA_ERROR);
  1113.       GET_UCHAR(BZ_X_ENDHDR_4, uc);
  1114.       if (uc != 0x38) RETURN(BZ_DATA_ERROR);
  1115.       GET_UCHAR(BZ_X_ENDHDR_5, uc);
  1116.       if (uc != 0x50) RETURN(BZ_DATA_ERROR);
  1117.       GET_UCHAR(BZ_X_ENDHDR_6, uc);
  1118.       if (uc != 0x90) RETURN(BZ_DATA_ERROR);
  1119.  
  1120.       s->storedCombinedCRC = 0;
  1121.       GET_UCHAR(BZ_X_CCRC_1, uc);
  1122.       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((ULONG)uc);
  1123.       GET_UCHAR(BZ_X_CCRC_2, uc);
  1124.       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((ULONG)uc);
  1125.       GET_UCHAR(BZ_X_CCRC_3, uc);
  1126.       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((ULONG)uc);
  1127.       GET_UCHAR(BZ_X_CCRC_4, uc);
  1128.       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((ULONG)uc);
  1129.  
  1130.       s->state = BZ_X_IDLE;
  1131.       RETURN(BZ_STREAM_END);
  1132.  
  1133.       default:  return BZ_SEQUENCE_ERROR;
  1134.    }
  1135.  
  1136.    return BZ_SEQUENCE_ERROR;
  1137.  
  1138.    save_state_and_return:
  1139.  
  1140.    s->save_i           = i;
  1141.    s->save_j           = j;
  1142.    s->save_t           = t;
  1143.    s->save_alphaSize   = alphaSize;
  1144.    s->save_nGroups     = nGroups;
  1145.    s->save_nSelectors  = nSelectors;
  1146.    s->save_EOB         = EOB;
  1147.    s->save_groupNo     = groupNo;
  1148.    s->save_groupPos    = groupPos;
  1149.    s->save_nextSym     = nextSym;
  1150.    s->save_nblockMAX   = nblockMAX;
  1151.    s->save_nblock      = nblock;
  1152.    s->save_es          = es;
  1153.    s->save_N           = N;
  1154.    s->save_curr        = curr;
  1155.    s->save_zt          = zt;
  1156.    s->save_zn          = zn;
  1157.    s->save_zvec        = zvec;
  1158.    s->save_zj          = zj;
  1159.    s->save_gSel        = gSel;
  1160.    s->save_gMinlen     = gMinlen;
  1161.    s->save_gLimit      = gLimit;
  1162.    s->save_gBase       = gBase;
  1163.    s->save_gPerm       = gPerm;
  1164.  
  1165.    return retVal;   
  1166. }
  1167.  
  1168. /*---------------------------------------------------*/
  1169. int BZ2_bzDecompressInit(bz_stream* strm, int verbosity, int small) {
  1170.    DState* s;
  1171.  
  1172.    if (strm == NULL) return BZ_PARAM_ERROR;
  1173.    if (small != 0 && small != 1) return BZ_PARAM_ERROR;
  1174.    if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR;
  1175.  
  1176.    s = BZALLOC( sizeof(DState) );
  1177.    if (s == NULL) return BZ_MEM_ERROR;
  1178.    s->strm                  = strm;
  1179.    strm->state              = s;
  1180.    s->state                 = BZ_X_MAGIC_1;
  1181.    s->bsLive                = 0;
  1182.    s->bsBuff                = 0;
  1183.    s->calculatedCombinedCRC = 0;
  1184.    strm->total_in_lo32      = 0;
  1185.    strm->total_in_hi32      = 0;
  1186.    strm->total_out_lo32     = 0;
  1187.    strm->total_out_hi32     = 0;
  1188.    s->smallDecompress       = (BOOL)small;
  1189.    s->ll4                   = NULL;
  1190.    s->ll16                  = NULL;
  1191.    s->tt                    = NULL;
  1192.    s->currBlockNo           = 0;
  1193.    s->verbosity             = verbosity;
  1194.  
  1195.    BZ2_MakeCRC32R(BZ2_crc32Table, 0x04C11DB7);
  1196.  
  1197.    return BZ_OK;
  1198. }
  1199.  
  1200.  
  1201. /*---------------------------------------------------*/
  1202. static
  1203. void unRLE_obuf_to_output_FAST ( DState* s )
  1204. {
  1205.    UBYTE k1;
  1206.  
  1207.    if (s->blockRandomised) {
  1208.  
  1209.       while (TRUE) {
  1210.          /* try to finish existing run */
  1211.          while (TRUE) {
  1212.             if (s->strm->avail_out == 0) return;
  1213.             if (s->state_out_len == 0) break;
  1214.             *( (UBYTE*)(s->strm->next_out) ) = s->state_out_ch;
  1215.             BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
  1216.             s->state_out_len--;
  1217.             s->strm->next_out++;
  1218.             s->strm->avail_out--;
  1219.             s->strm->total_out_lo32++;
  1220.             if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
  1221.          }
  1222.    
  1223.          /* can a new run be started? */
  1224.          if (s->nblock_used == s->save_nblock+1) return;
  1225.                
  1226.    
  1227.          s->state_out_len = 1;
  1228.          s->state_out_ch = s->k0;
  1229.          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 
  1230.          k1 ^= BZ_RAND_MASK; s->nblock_used++;
  1231.          if (s->nblock_used == s->save_nblock+1) continue;
  1232.          if (k1 != s->k0) { s->k0 = k1; continue; };
  1233.    
  1234.          s->state_out_len = 2;
  1235.          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 
  1236.          k1 ^= BZ_RAND_MASK; s->nblock_used++;
  1237.          if (s->nblock_used == s->save_nblock+1) continue;
  1238.          if (k1 != s->k0) { s->k0 = k1; continue; };
  1239.    
  1240.          s->state_out_len = 3;
  1241.          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 
  1242.          k1 ^= BZ_RAND_MASK; s->nblock_used++;
  1243.          if (s->nblock_used == s->save_nblock+1) continue;
  1244.          if (k1 != s->k0) { s->k0 = k1; continue; };
  1245.    
  1246.          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 
  1247.          k1 ^= BZ_RAND_MASK; s->nblock_used++;
  1248.          s->state_out_len = ((LONG)k1) + 4;
  1249.          BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK; 
  1250.          s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
  1251.       }
  1252.  
  1253.    } else {
  1254.  
  1255.       /* restore */
  1256.       ULONG        c_calculatedBlockCRC = s->calculatedBlockCRC;
  1257.       UBYTE         c_state_out_ch       = s->state_out_ch;
  1258.       LONG         c_state_out_len      = s->state_out_len;
  1259.       LONG         c_nblock_used        = s->nblock_used;
  1260.       LONG         c_k0                 = s->k0;
  1261.       ULONG*       c_tt                 = s->tt;
  1262.       ULONG        c_tPos               = s->tPos;
  1263.       char*         cs_next_out          = s->strm->next_out;
  1264.       unsigned int  cs_avail_out         = s->strm->avail_out;
  1265.       /* end restore */
  1266.  
  1267.       ULONG       avail_out_INIT = cs_avail_out;
  1268.       LONG        s_save_nblockPP = s->save_nblock+1;
  1269.       unsigned int total_out_lo32_old;
  1270.  
  1271.       while (TRUE) {
  1272.  
  1273.          /* try to finish existing run */
  1274.          if (c_state_out_len > 0) {
  1275.             while (TRUE) {
  1276.                if (cs_avail_out == 0) goto return_notr;
  1277.                if (c_state_out_len == 1) break;
  1278.                *( (UBYTE*)(cs_next_out) ) = c_state_out_ch;
  1279.                BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
  1280.                c_state_out_len--;
  1281.                cs_next_out++;
  1282.                cs_avail_out--;
  1283.             }
  1284.             s_state_out_len_eq_one:
  1285.             {
  1286.                if (cs_avail_out == 0) { 
  1287.                   c_state_out_len = 1; goto return_notr;
  1288.                };
  1289.                *( (UBYTE*)(cs_next_out) ) = c_state_out_ch;
  1290.                BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
  1291.                cs_next_out++;
  1292.                cs_avail_out--;
  1293.             }
  1294.          }   
  1295.          /* can a new run be started? */
  1296.          if (c_nblock_used == s_save_nblockPP) {
  1297.             c_state_out_len = 0; goto return_notr;
  1298.          };   
  1299.          c_state_out_ch = c_k0;
  1300.          BZ_GET_FAST_C(k1); c_nblock_used++;
  1301.          if (k1 != c_k0) { 
  1302.             c_k0 = k1; goto s_state_out_len_eq_one; 
  1303.          };
  1304.          if (c_nblock_used == s_save_nblockPP) 
  1305.             goto s_state_out_len_eq_one;
  1306.    
  1307.          c_state_out_len = 2;
  1308.          BZ_GET_FAST_C(k1); c_nblock_used++;
  1309.          if (c_nblock_used == s_save_nblockPP) continue;
  1310.          if (k1 != c_k0) { c_k0 = k1; continue; };
  1311.    
  1312.          c_state_out_len = 3;
  1313.          BZ_GET_FAST_C(k1); c_nblock_used++;
  1314.          if (c_nblock_used == s_save_nblockPP) continue;
  1315.          if (k1 != c_k0) { c_k0 = k1; continue; };
  1316.    
  1317.          BZ_GET_FAST_C(k1); c_nblock_used++;
  1318.          c_state_out_len = ((LONG)k1) + 4;
  1319.          BZ_GET_FAST_C(c_k0); c_nblock_used++;
  1320.       }
  1321.  
  1322.       return_notr:
  1323.       total_out_lo32_old = s->strm->total_out_lo32;
  1324.       s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);
  1325.       if (s->strm->total_out_lo32 < total_out_lo32_old)
  1326.          s->strm->total_out_hi32++;
  1327.  
  1328.       /* save */
  1329.       s->calculatedBlockCRC = c_calculatedBlockCRC;
  1330.       s->state_out_ch       = c_state_out_ch;
  1331.       s->state_out_len      = c_state_out_len;
  1332.       s->nblock_used        = c_nblock_used;
  1333.       s->k0                 = c_k0;
  1334.       s->tt                 = c_tt;
  1335.       s->tPos               = c_tPos;
  1336.       s->strm->next_out     = cs_next_out;
  1337.       s->strm->avail_out    = cs_avail_out;
  1338.       /* end save */
  1339.    }
  1340. }
  1341.  
  1342.  
  1343.  
  1344. /*---------------------------------------------------*/
  1345. static
  1346. void unRLE_obuf_to_output_SMALL ( DState* s )
  1347. {
  1348.    UBYTE k1;
  1349.  
  1350.    if (s->blockRandomised) {
  1351.  
  1352.       while (TRUE) {
  1353.          /* try to finish existing run */
  1354.          while (TRUE) {
  1355.             if (s->strm->avail_out == 0) return;
  1356.             if (s->state_out_len == 0) break;
  1357.             *( (UBYTE*)(s->strm->next_out) ) = s->state_out_ch;
  1358.             BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
  1359.             s->state_out_len--;
  1360.             s->strm->next_out++;
  1361.             s->strm->avail_out--;
  1362.             s->strm->total_out_lo32++;
  1363.             if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
  1364.          }
  1365.    
  1366.          /* can a new run be started? */
  1367.          if (s->nblock_used == s->save_nblock+1) return;
  1368.                
  1369.    
  1370.          s->state_out_len = 1;
  1371.          s->state_out_ch = s->k0;
  1372.          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 
  1373.          k1 ^= BZ_RAND_MASK; s->nblock_used++;
  1374.          if (s->nblock_used == s->save_nblock+1) continue;
  1375.          if (k1 != s->k0) { s->k0 = k1; continue; };
  1376.    
  1377.          s->state_out_len = 2;
  1378.          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 
  1379.          k1 ^= BZ_RAND_MASK; s->nblock_used++;
  1380.          if (s->nblock_used == s->save_nblock+1) continue;
  1381.          if (k1 != s->k0) { s->k0 = k1; continue; };
  1382.    
  1383.          s->state_out_len = 3;
  1384.          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 
  1385.          k1 ^= BZ_RAND_MASK; s->nblock_used++;
  1386.          if (s->nblock_used == s->save_nblock+1) continue;
  1387.          if (k1 != s->k0) { s->k0 = k1; continue; };
  1388.    
  1389.          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 
  1390.          k1 ^= BZ_RAND_MASK; s->nblock_used++;
  1391.          s->state_out_len = ((LONG)k1) + 4;
  1392.          BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK; 
  1393.          s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
  1394.       }
  1395.  
  1396.    } else {
  1397.  
  1398.       while (TRUE) {
  1399.          /* try to finish existing run */
  1400.          while (TRUE) {
  1401.             if (s->strm->avail_out == 0) return;
  1402.             if (s->state_out_len == 0) break;
  1403.             *( (UBYTE*)(s->strm->next_out) ) = s->state_out_ch;
  1404.             BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
  1405.             s->state_out_len--;
  1406.             s->strm->next_out++;
  1407.             s->strm->avail_out--;
  1408.             s->strm->total_out_lo32++;
  1409.             if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
  1410.          }
  1411.    
  1412.          /* can a new run be started? */
  1413.          if (s->nblock_used == s->save_nblock+1) return;
  1414.    
  1415.          s->state_out_len = 1;
  1416.          s->state_out_ch = s->k0;
  1417.          BZ_GET_SMALL(k1); s->nblock_used++;
  1418.          if (s->nblock_used == s->save_nblock+1) continue;
  1419.          if (k1 != s->k0) { s->k0 = k1; continue; };
  1420.    
  1421.          s->state_out_len = 2;
  1422.          BZ_GET_SMALL(k1); s->nblock_used++;
  1423.          if (s->nblock_used == s->save_nblock+1) continue;
  1424.          if (k1 != s->k0) { s->k0 = k1; continue; };
  1425.    
  1426.          s->state_out_len = 3;
  1427.          BZ_GET_SMALL(k1); s->nblock_used++;
  1428.          if (s->nblock_used == s->save_nblock+1) continue;
  1429.          if (k1 != s->k0) { s->k0 = k1; continue; };
  1430.    
  1431.          BZ_GET_SMALL(k1); s->nblock_used++;
  1432.          s->state_out_len = ((LONG)k1) + 4;
  1433.          BZ_GET_SMALL(s->k0); s->nblock_used++;
  1434.       }
  1435.  
  1436.    }
  1437. }
  1438.  
  1439.  
  1440. /*---------------------------------------------------*/
  1441. int BZ2_bzDecompress ( bz_stream *strm )
  1442. {
  1443.    DState* s;
  1444.    if (strm == NULL) return BZ_PARAM_ERROR;
  1445.    s = strm->state;
  1446.    if (s == NULL) return BZ_PARAM_ERROR;
  1447.    if (s->strm != strm) return BZ_PARAM_ERROR;
  1448.  
  1449.    while (TRUE) {
  1450.       if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR;
  1451.       if (s->state == BZ_X_OUTPUT) {
  1452.          if (s->smallDecompress)
  1453.             unRLE_obuf_to_output_SMALL ( s ); else
  1454.             unRLE_obuf_to_output_FAST  ( s );
  1455.          if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
  1456.             BZ_FINALISE_CRC ( s->calculatedBlockCRC );
  1457.             if (s->calculatedBlockCRC != s->storedBlockCRC)
  1458.                return BZ_DATA_ERROR;
  1459.             s->calculatedCombinedCRC 
  1460.                = (s->calculatedCombinedCRC << 1) | 
  1461.                     (s->calculatedCombinedCRC >> 31);
  1462.             s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
  1463.             s->state = BZ_X_BLKHDR_1;
  1464.          } else {
  1465.             return BZ_OK;
  1466.          }
  1467.       }
  1468.       if (s->state >= BZ_X_MAGIC_1) {
  1469.          LONG r = BZ2_decompress ( s );
  1470.          if (r == BZ_STREAM_END) {
  1471.             if (s->calculatedCombinedCRC != s->storedCombinedCRC)
  1472.                return BZ_DATA_ERROR;
  1473.             return r;
  1474.          }
  1475.          if (s->state != BZ_X_OUTPUT) return r;
  1476.       }
  1477.    }
  1478.  
  1479.    return BZ_SEQUENCE_ERROR;  /*NOTREACHED*/
  1480. }
  1481.  
  1482.  
  1483. /*---------------------------------------------------*/
  1484. int BZ2_bzDecompressEnd  ( bz_stream *strm )
  1485. {
  1486.    DState* s;
  1487.    if (strm == NULL) return BZ_PARAM_ERROR;
  1488.    s = strm->state;
  1489.    if (s == NULL) return BZ_PARAM_ERROR;
  1490.    if (s->strm != strm) return BZ_PARAM_ERROR;
  1491.  
  1492.    if (s->tt   != NULL) BZFREE(s->tt);
  1493.    if (s->ll16 != NULL) BZFREE(s->ll16);
  1494.    if (s->ll4  != NULL) BZFREE(s->ll4);
  1495.  
  1496.    BZFREE(strm->state);
  1497.    strm->state = NULL;
  1498.  
  1499.    return BZ_OK;
  1500. }
  1501.  
  1502. /*-------------------------------------------------------------*/
  1503. /*--- end                                                   ---*/
  1504. /*-------------------------------------------------------------*/
  1505.  
  1506.  
  1507. /*--- memory functions -----------------------------------------------------*/
  1508.  
  1509. struct xadMasterBase *xadBase;
  1510.  
  1511. struct mh {
  1512.   struct mh *next;
  1513.   ULONG pad; /* for gcc alignment problems on 64-bit machines */
  1514. };
  1515.  
  1516. struct mh *initmem(XADBASE) {
  1517.   struct mh *base = (struct mh *) xadAllocVec(sizeof(struct mh), 0);
  1518.   xadBase = xadMasterBase;
  1519.   if (base) base->next = NULL;
  1520.   return base;
  1521. }
  1522.  
  1523. APTR allocmem(struct mh *base, ULONG size, ULONG flags) {
  1524.   struct xadMasterBase *xadMasterBase = xadBase;
  1525.   struct mh *mem = (struct mh *) xadAllocVec(size + sizeof(struct mh), flags);
  1526.   if (!mem) return NULL;
  1527.   mem->next = base->next; /* link into list */
  1528.   base->next = mem;
  1529.   return (APTR) ++mem;
  1530. }
  1531.  
  1532. void freemem(struct mh *base, APTR mem) {
  1533.   struct xadMasterBase *xadMasterBase = xadBase;
  1534.   struct mh *m, *x, *o;
  1535.  
  1536.   if (!mem || !base) return;
  1537.   m = (struct mh *) mem;  m--; /* get correct address */
  1538.  
  1539.   for (o = base; (x = o->next); o = x) {
  1540.     if (x == m) {
  1541.       o->next = x->next;
  1542.       xadFreeObjectA((APTR)x, NULL);
  1543.       return;
  1544.     }
  1545.   }
  1546. }
  1547.  
  1548. void freeallmem(struct mh *base) {
  1549.   struct xadMasterBase *xadMasterBase = xadBase;
  1550.   while (base) {
  1551.     struct mh *next = base->next;
  1552.     xadFreeObjectA((APTR)base, NULL);
  1553.     base = next;
  1554.   }
  1555. }
  1556.  
  1557.  
  1558. /*--- xad slave -------------------------------------------------------------*/
  1559.  
  1560. ASM(BOOL) bzip2_RecogData(REG(d0, ULONG size), REG(a0, STRPTR data), XADBASE) {
  1561.  
  1562.   /* check file header */
  1563.   if (data[0] != 'B' || data[1] != 'Z' || data[2] != 'h') return 0;
  1564.   if (data[3] <  '1' || data[3] > '9') return 0;
  1565.  
  1566.   /* check first block header */
  1567.  
  1568.   if (data[4] == 0x31) {
  1569.     if (data[5] != 0x41 || data[6] != 0x59) return 0;
  1570.     if (data[7] != 0x26 || data[8] != 0x53 || data[9] != 0x59) return 0;
  1571.   }
  1572.   else {
  1573.     if (data[4] != 0x17 || data[5] != 0x72 || data[6] != 0x45) return 0;
  1574.     if (data[7] != 0x38 || data[8] != 0x50 || data[9] != 0x90) return 0;
  1575.   }  
  1576.  
  1577.   /* we're happy with it */
  1578.   return 1;
  1579. }
  1580.  
  1581. /* clips .bz or .bz2, changes .tbz or .tbz2 to .tar */
  1582. void bzip2_change_ext(char *p) {
  1583.   char c;
  1584.   if ((c = *--p) == '2') c = *--p;
  1585.   if (c == 'Z' || c == 'z') c = *--p; else return;
  1586.   if (c == 'B' || c == 'b') c = *--p; else return;
  1587.   if (c == '.') *p = '\0';
  1588.   else if ((c == 'T' || c == 't') && p[-1] == '.') {
  1589.     *p++ = 't'; *p++ = 'a'; *p++ = 'r'; *p = '\0';
  1590.   }
  1591. }
  1592.  
  1593. ASM(LONG) bzip2_GetInfo(REG(a0, struct xadArchiveInfo *ai), XADBASE) {
  1594.   struct TagItem tags[]  = {
  1595.     { XAD_OBJNAMESIZE, 0 },
  1596.     { TAG_DONE, 0 }
  1597.   };
  1598.  
  1599.   struct TagItem datetags[] = {
  1600.     { XAD_DATECURRENTTIME, 1 },
  1601.     { XAD_GETDATEXADDATE,  0 },
  1602.     { TAG_DONE, 0 }
  1603.   };
  1604.  
  1605.   /* there's only one file in a bzip archive - the uncompressed data */
  1606.   struct xadFileInfo *fi;
  1607.  
  1608.   char *name;
  1609.   int namelen;
  1610.  
  1611.   /* do we have a filename for this archive? */
  1612.   if ((name = ai->xai_InName)) tags[0].ti_Data = namelen = (strlen(name) + 1);
  1613.  
  1614.   /* allocate a fileinfo structure */
  1615.   if (!(ai->xai_FileInfo = fi = (struct xadFileInfo *) xadAllocObjectA(
  1616.     XADOBJ_FILEINFO, (name) ? tags : NULL))) return XADERR_NOMEMORY;
  1617.  
  1618.   fi->xfi_Flags = XADFIF_NODATE | XADFIF_NOUNCRUNCHSIZE | XADFIF_SEEKDATAPOS;
  1619.   fi->xfi_EntryNumber = 1;
  1620.   fi->xfi_CrunchSize  = ai->xai_InSize - 14;
  1621.   fi->xfi_Size        = 0;
  1622.   fi->xfi_DataPos     = 0;
  1623.  
  1624.   /* fill in today's date */
  1625.   datetags[1].ti_Data = (ULONG) &fi->xfi_Date;
  1626.   xadConvertDatesA(datetags);
  1627.  
  1628.   if (name) {
  1629.     xadCopyMem(ai->xai_InName, (name = fi->xfi_FileName), namelen);
  1630.     bzip2_change_ext(name + namelen - 1);
  1631.   }
  1632.   else {
  1633.     fi->xfi_FileName = xadMasterBase->xmb_DefaultName;
  1634.     fi->xfi_Flags   |= XADFIF_NOFILENAME;
  1635.   }
  1636.  
  1637.   return XADERR_OK;
  1638. }
  1639.  
  1640.  
  1641. /* bz2lib support functions */
  1642. void *bzalloc(void *base, int a, int b) {
  1643.   return allocmem((struct mh *)base, a*b, 0);
  1644. }
  1645. void bzfree(void *base, void *mem) {
  1646.   freemem((struct mh *)base, mem);
  1647. }
  1648.  
  1649.  
  1650. ASM(LONG) SAVEDS bzip2_UnArchive(REG(a0, struct xadArchiveInfo *ai), XADBASE) {
  1651.   struct mh *base;
  1652.   char *buf_in, *buf_out, once_ok=0;
  1653.   const int bufsize = 8192;
  1654.   int size;
  1655.   bz_stream bzs;
  1656.   LONG err, bzerr;
  1657.  
  1658.   /* ensure we're decrunching our only file! */
  1659.   if (!ai || !ai->xai_CurFile || ai->xai_CurFile->xfi_EntryNumber != 1)
  1660.     return XADERR_BADPARAMS;
  1661.  
  1662.   /* initialise memory system */
  1663.   ai->xai_PrivateClient = (APTR) (base = initmem(xadMasterBase));
  1664.   bzs.opaque    = base;
  1665.   bzs.bzalloc   = bzalloc;
  1666.   bzs.bzfree    = bzfree;
  1667.  
  1668.   /* allocate some buffers */
  1669.   buf_in  = allocmem(base, bufsize, 1);
  1670.   buf_out = allocmem(base, bufsize, 1);
  1671.   if (!buf_in || !buf_out) return XADERR_NOMEMORY;
  1672.  
  1673.   /* force immediate read-in of data on first run only */
  1674.   bzs.avail_in = 0;
  1675.  
  1676.   /* always keep going - exit is only when demand passes EOF */
  1677.   while (1) {
  1678.     /* initialise the decompression state */
  1679.     if ((bzerr=BZ2_bzDecompressInit(&bzs, 0, 0)) != BZ_OK)
  1680.       return XADERR_NOMEMORY;
  1681.  
  1682.     /* reset output buffer */
  1683.     bzs.avail_out = bufsize;
  1684.     bzs.next_out  = buf_out;
  1685.  
  1686.     while (bzerr == BZ_OK) {
  1687.       /* fill input buffer when empty */
  1688.       if (bzs.avail_in == 0) {
  1689.         size = ai->xai_InSize - ai->xai_InPos;
  1690.         if (size > bufsize) size = bufsize;
  1691.         if (size == 0) return XADERR_OK; /** normal exit point = EOF **/
  1692.         if((err = xadHookAccess(XADAC_READ, size, buf_in, ai))) return err;
  1693.         bzs.next_in  = buf_in;
  1694.         bzs.avail_in = size;
  1695.       }
  1696.  
  1697.       /* do some more decompression */
  1698.       bzerr = BZ2_bzDecompress(&bzs);
  1699.  
  1700.       /* purge any output */
  1701.       if ((size = bufsize - bzs.avail_out) > 0) {
  1702.         if((err = xadHookAccess(XADAC_WRITE, size, buf_out, ai))) return err;
  1703.         bzs.next_out  = buf_out;
  1704.         bzs.avail_out = bufsize;
  1705.       }
  1706.     }
  1707.  
  1708.     switch (bzerr) {
  1709.     case BZ_STREAM_END:       once_ok = 1; BZ2_bzDecompressEnd(&bzs); break;
  1710.     case BZ_DATA_ERROR:       return XADERR_ILLEGALDATA;
  1711.     case BZ_DATA_ERROR_MAGIC: return once_ok ? XADERR_OK : XADERR_ILLEGALDATA;
  1712.     case BZ_MEM_ERROR:        return XADERR_NOMEMORY;
  1713.     default:                  return XADERR_DECRUNCH;
  1714.     }
  1715.   }
  1716.   return XADERR_DECRUNCH; /* not reached! */
  1717. }
  1718.  
  1719.  
  1720. ASM(void) SAVEDS bzip2_Free(REG(a0, struct xadArchiveInfo *ai), XADBASE) {
  1721.   freeallmem((struct mh *) ai->xai_PrivateClient);
  1722.   ai->xai_PrivateClient = NULL;
  1723. }
  1724.  
  1725.  
  1726. const struct xadClient bzip2_Client = {
  1727.   NEXTCLIENT, XADCLIENT_VERSION, 7, BZIP2_VERSION, BZIP2_REVISION,
  1728.  
  1729.   14,                        /* minimum archive size     */
  1730.   XADCF_FILEARCHIVER | XADCF_FREEFILEINFO,    /* type of client and flags */
  1731.   0,                        /* internal ID (not needed) */
  1732.   "BZip2",                    /* name of client           */
  1733.  
  1734.   /* client functions */
  1735.   (BOOL (*)()) bzip2_RecogData,
  1736.   (LONG (*)()) bzip2_GetInfo,
  1737.   (LONG (*)()) bzip2_UnArchive,
  1738.   (void (*)()) bzip2_Free
  1739. };
  1740.